package org.hw.algorithm.leetcode.array;

/**
 * @author hewei
 * @date 2023.4.26
 * <h>题目描述：11. 盛最多水的容器</h>
 * <p>
 *     给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
 *
 * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 *
 * 返回容器可以储存的最大水量。
 *
 * 说明：你不能倾斜容器。
 *
 *  
 *
 * 示例 1：
 *
 *
 *
 * 输入：[1,8,6,2,5,4,8,3,7]
 * 输出：49
 * 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
 * 示例 2：
 *
 * 输入：height = [1,1]
 * 输出：1
 *  
 *
 * 提示：
 *
 * n == height.length
 * 2 <= n <= 105
 * 0 <= height[i] <= 104
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/container-with-most-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * </p>
 * <h>题解</h>
 * <p>
 *     一、暴力循环法（不满足时间）
 *     总体思路还是比较笨的办法，进行逐个乘积的比较。从第一个高度开始，逐个计算面积，如果比上次计算的面积大，则最大面积为当前面积。
 *     1.面积=长X高。长=x轴坐标（就是数组下标）,高=y轴坐标（就是数组的值）
 *     2.从第一个高度开始，计算其与后面的高度中最小值 与 宽度（下标的差值）的乘积
 *     3.取这些乘积中最大的值返回
 *     二、双指针法
 *     优化暴力循环法，将从第一个高度开始逐个匹配改为从数组两端开始计算取最大容积，在计算过程中是通过逐渐淘汰最小容积的思路。
 *
 * </p>
 *
 */
public class LeetCodeArray11 {

    public static void main(String[] args) {
        int[] array = {1,8,6,2,5,4,8,3,7};
//        System.out.println(maxVolumeForeach(array));
        System.out.println(maxVolumeDpoint(array));
//        System.out.println(maxArea(array));
    }

    /*循环法*/
    public static int maxVolumeForeach(int[] arr){
        int maxVolume=0;
        for(int i=0; i<arr.length-1; i++){
            for (int j=i+1;j<arr.length; j++){
                int tempVolume=Math.min(arr[j],arr[i])*(j-i);
                if (maxVolume<tempVolume){
                    maxVolume=tempVolume;
                }
            }
        }
        return maxVolume;
    }
    /*双指针法*/
    public static int maxVolumeDpoint(int[] arr){
        int maxVolume=0;
        for(int i=0,j=arr.length-1; i < j; ){
            int tempVolume = arr[i] < arr[j] ? (j - i) * arr[i++]  : (j - i) * arr[j--] ;
            maxVolume = Math.max(tempVolume,maxVolume);
        }
        return maxVolume;
    }

}